package 剑指offer;

import java.util.Iterator;
import java.util.LinkedList;

public class 数据流中的中位数 {
    private static LinkedList<Integer> list = new LinkedList<>();
    public static void main(String[] args) {
	Insert(1);
	Insert(5);
	Insert(4);
	Insert(3);
	System.out.println(GetMedian());
    }
    public static void Insert(Integer num) {
	Iterator<Integer> iterator = list.iterator();
	Boolean flag = false;
	int index = -1;
	if(list.size()==0) {
	    list.add(num);
	}else {
	    for(Integer e:list) {
		index++;
		if(e>num) {
		    flag = true;
		  break;
		}
	    }
	    if(flag) {
		list.add(index, num);
		return ;
	    }
	    list.add(num);
	   
	}
    }

    public static Double GetMedian() {
	
	if(list.size()%2==1) {
	    return Double.parseDouble(list.get((list.size()/2)).toString());
	}
	return  ((new Double(list.get((list.size()/2)).toString()))+
		new Double(list.get((list.size()/2-1)).toString()))/2;

    }

}
